#include <bits/stdc++.h>

using namespace std;

void dfs(vector<int>& candidates, int sum, int target);

vector<vector<int>> combinationSum(vector<int>& candidates, int target);

int main()
{
	return 0;
}

vector<bool> vis;
vector<int> layer;
vector<vector<int>> res;

vector<vector<int>> combinationSum(vector<int>& candidates, int target)
{
	sort(candidates.begin(), candidates.end());
	vis.resize(candidates.size(), false);
	dfs(candidates, 0, target);

	return res;
}

void dfs(vector<int>& candidates, int sum, int target)
{
	if (sum == target) {
		res.emplace_back(layer);
		return;
	}
	if (sum + candidates[0] > target) return;

	for (int i = 0, len = candidates.size(); i < len; i++) {
		if (layer.size() > 0 && candidates[i] < layer.back()) continue;
		if (vis[i] && layer.size() > 0 && layer.back() != candidates[i]) continue;

		vis[i] = true;
		layer.emplace_back(candidates[i]);
		dfs(candidates, sum + candidates[i], target);
		layer.pop_back();
		vis[i] = false;
	}
}
